The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet. For example, an enqueuing component of such a device receives a stream of various sized packets which are accumulated in an input buffer. Each packet is analyzed, and an appropriate amount of memory space is allocated to store the packet. The packet is stored in memory, while certain attributes (e.g., destination information and other information typically derived from a packet header or other source) are maintained in separate memory. Once the entire packet is written into memory, the packet becomes eligible for processing, and an indicator of the packet is typically placed in an appropriate destination queue for being serviced according to some scheduling methodology.
In some communications devices, one or more output queues are mapped into one or more output ports. These output queues may contain traffic data with specific quality of service characteristics, while the output ports typically represent specific physical output interfaces and/or unique traffic groups which may be processed further within the communication device before being mapped to the actual physical output port. This processing typically requires an efficient hardware implementation for mapping a set of N output queues (typically labeled 0 to N−1) to a set of M output ports (typically labeled 0 to M−1). In one system, any output queue may be mapped to a single output port, and any output port can be mapped to zero or more (up to N−1) output queues. The mapping mechanism should allow a decision for selecting an output queue from the set of N possible output queues based on what queues are mapped to the current output port, the state of an output queue, and the type of traffic maintained an output queue.
One known approach uses a bit mask representing output queue to port mapping. This approach requires an M×N bit array representing an N bit mask for every output queue (0 . . . N−1). When scheduling output queue n (0 . . . N−1), the appropriate mask is used to mask only the appropriate output queues. One drawback of this method is the large memory requirement. For example, for a 2048*8192 mapping, a 16 Mbit internal chip memory is required.
One known approach uses a low/high range table. This method restricts the mapping by requiring each output queue to be mapped only to a sequential set of output queues. When scheduling output queue n (0 . . . N−1), the low/high entries for this output queue are used to drive a mask generator masking the irrelevant output queues. The table required by this method uses 2*log2(N)*M bits. One drawback of this method is the inflexibility caused by the requirement of contiguous output ports. This prevents adding an output queue to an output port without remapping all other output queues.
One known approach uses a linked list. This approach links all queues that are mapped to a specific output port on a linked list, and maintains this linked list. One advantage of this method is that linked lists can be easily updated dynamically. One drawback is that if the current queue at the top of the linked list is not ready for scheduling, the next list item needs to be read. This means that the scheduling time is bounded by N linked list lookups which may take a significant amount of time. A variation on this scheme maintains more than one list for each port, wherein there is a separate list for queues that are ready for scheduling. Some problems of this approach may include design complexity caused by coherency issues (e.g., simultaneous dequeue/enqueue), a large number of special cases when the list is almost empty, and multiple sequential memory accesses required for each operation.